返回

小白月赛105 - 题目 C

• 本题目是有关”关节点”的图论问题。
• 但是也可以通过找规律的方式做出
• 这里我们讲解一下找规律的思路过程

思路

• 出发点是找到所有能影响连通性的点.
  • 那怎么样才会影响联通性呢?
    • 发现如果一个点是俩集合的交点, 那么去掉这个点之后(交点为一个否则不行), 这俩集合就无法联通了.这样会让联通块++
      • 那怎么找到这样的集合以及交点呢?
        • 我们可以在二维地图的每个节点的邻接节点进行关系并查集合并，这样就可以找到所有的联通图了
        • 我们只需要再遍历一下每个位置，看看他的所有邻接点的联通图是不是同一个，如果不是，那么这个点就是一个交点，去掉这个点之后，联通块数量将会++
    • 如果一个点就是一个孤立的集合, 那么去掉这个点之后, 联通块数量将会–
      • 而且我们发现只有这种情况才会–
• 我们以上总结了可能会影响联通性的情况